Prim Algorithm

프림 알고리즘(Prim Algorithm)
Set이 아닌 트리가 자라나는 방향으로 최소 신장 트리르 구성

각 트리는 고립된 정점을 연결하는 경량 간선을 A에 추가(안전한 간선)
#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#define NIL -1
using namespace std;
struct Node{
int value;
Node* next=nullptr;
Node(int _value): value(_value) {}
};
struct Vertex{
int key=INT_MAX, pi=NIL;
Vertex(){}
};
struct adjList{
Node** aL;
Vertex* vertex;
int vN, eN;
adjList(int _vN, int E[][2], int _eN): vN(_vN), eN(_eN){
vertex=new Vertex[this->vN];
aL=new Node*[this->vN];
for(int i=0; i<this->eN; ++i){
Node* nN1=new Node(E[i][1]);
Node* nN2=new Node(E[i][0]);
if(aL[E[i][0]-1]==nullptr){
aL[E[i][0]-1]=nN1;
} else {
Node* tmp=aL[E[i][0]-1];
aL[E[i][0]-1]=nN1;
nN1->next=tmp;
}
if(aL[E[i][1]-1]==nullptr){
aL[E[i][1]-1]=nN2;
} else {
Node* tmp=aL[E[i][1]-1];
aL[E[i][1]-1]=nN2;
nN2->next=tmp;
}
}
}
~adjList(){
// Chain List 삭제를 고려하지 않았음
for(int i=0; i<this->vN; ++i) delete[] aL[i];
delete[] vertex;
delete[] aL;
}
};
struct VertexInfo{
int vertexNo;
int* key;
VertexInfo(int _vertexNo, int* _key): vertexNo(_vertexNo), key(_key){}
bool operator<(const VertexInfo other) const {
return *(this->key)>*(other.key);
}
};
struct retList{
int* data;
int cap=0, sz;
retList(int _sz): sz(_sz) {
this->data=new int[this->sz];
}
~retList(){
delete data;
}
void Insert(int val){
if(this->cap==this->sz){
perror("OVERFLOW");
exit(1);
}
data[cap++]=val;
}
void print(void){
for(int i=0; i<this->cap; ++i){
std::cout<<this->data[i]<<' ';
}
std::cout<<std::endl;
}
};
retList* MST_Prim(adjList* graph, int* w, int r, int E[][2]){
std::vector<VertexInfo> Q;
//std::priority_queue<VertexInfo> Q;
retList* A=new retList(graph->vN);
bool* isMember=new bool[graph->vN];
for(int i=0; i<graph->vN; ++i){
graph->vertex[i].key=INT_MAX;
graph->vertex[i].pi=NIL;
}
graph->vertex[r-1].key=0;
for(int i=0; i<graph->vN; ++i){
//Q.push(VertexInfo(i+1, &graph->vertex[i].key));
Q.push_back(VertexInfo(i+1, & graph->vertex[i].key));
isMember[i]=true;
};
while(!Q.empty()){
//int u=Q.top().vertexNo;
std::sort(Q.begin(), Q.end());
int u=Q.back().vertexNo;
Q.pop_back();
// Q.pop();
isMember[u-1]=false;
A->Insert(u);
Node* cur=graph->aL[u-1];
while(cur!=nullptr){
int v=cur->value;
int wInd=-1;
// need to optimize search algorithm to trees
for(int i=0; i<graph->eN; ++i){
if((E[i][0]==u && E[i][1]==v) || (E[i][1]==u && E[i][0]==v)){
wInd=i;
break;
}
}
if(isMember[v-1] && w[wInd]<graph->vertex[v-1].key){
graph->vertex[v-1].pi=u;
graph->vertex[v-1].key=w[wInd];
}
cur=cur->next;
}
}
delete[] isMember;
return A;
}
int main(void){
int E[14][2]={
{1, 2}, {1, 8}, {2, 3}, {2, 8}, {3, 4}, {3, 6}, {3, 9},
{4, 5}, {4, 6}, {5, 6}, {6, 7}, {7, 8}, {7, 9}, {8, 9}
};
int weight[14]={4, 8, 8, 11, 7, 4, 2, 9, 14, 10, 2, 1, 6, 7};
adjList* graph=new adjList(9, E, 14);
retList* A=MST_Prim(graph, weight, 1, E);
A->print();
delete graph;
delete A;
return 0;
}